// Copyright 2011 Chris Hamilton (chhamilton@gmail.com)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include <algorithm>
#include <map>
#include <vector>
#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <unistd.h>
#include <X11/extensions/Xrandr.h>
#include <X11/Xatom.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>

// Stores error message info.
struct Error {
  std::string message;
  std::string filename;
  std::string function;
  int line;
  Error(const char* msg, const char* fn, const char* f, int l):
    message(msg),
    filename(fn),
    function(f),
    line(l)
  {}
};
std::vector<Error> gErrorStack;
char gErrorBuffer[1024];
#define _PushError(file, function, line, args...) { \
          snprintf(gErrorBuffer, sizeof(gErrorBuffer), args); \
          gErrorStack.push_back(Error(gErrorBuffer, file, function, line)); \
        }

#define PushError(args...) _PushError(__FILE__, __FUNCTION__, __LINE__, args)

void ClearErrorStack() {
  gErrorStack.clear();
}

void DumpErrorStack() {
  for (int i = 0; i < (int)gErrorStack.size(); ++i) {
    fprintf(stderr, "error(%s:%s:%d): %s\n",
      gErrorStack[i].filename.c_str(),
      gErrorStack[i].function.c_str(),
      gErrorStack[i].line,
      gErrorStack[i].message.c_str());
  }
}

#define Die(args...) { PushError(args); DumpErrorStack(); exit(1); }

#define CloseDisplayAndDie(display, args...) { \
          XCloseDisplay(display); \
          Die(args); \
        }

#define PushErrorWrap(cmd, args...) { \
          if (!cmd(args)) { \
            PushError("" # cmd "failed"); \
            return false; \
          } \
        }

#define IMPLEMENT_STRUCT_EQ(T) \
  bool operator==(const T& rhs) const { \
    return memcmp((const void*)this, (const void*)&rhs, sizeof(T))==0; \
  } \
  bool operator!=(const T& rhs) const { \
    return memcmp((const void*)this, (const void*)&rhs, sizeof(T))!=0; \
  }

struct Position {
  long x;
  long y;
  IMPLEMENT_STRUCT_EQ(Position)
  void dump(FILE* f = stdout, bool eol = true) const {
    fprintf(f, "Position(x=%ld, y=%ld)", x, y);
    if (eol) fputc('\n', f);
    fflush(f);
  }
};

struct Geometry {
  long width;
  long height;
  IMPLEMENT_STRUCT_EQ(Geometry)
  void dump(FILE* f = stdout, bool eol = true) const {
    fprintf(f, "Geometry(w=%ld, h=%ld)", width, height);
    if (eol) fputc('\n', f);
    fflush(f);
  }
};

struct Area {
  long x;
  long y;
  long width;
  long height;
  long area() const { return width*height; }
  IMPLEMENT_STRUCT_EQ(Area)
  Area intersection(const Area& a2) const {
    Area a;
    a.x = std::max(x, a2.x);
    a.y = std::max(y, a2.y);
    long x2 = std::min(x + width, a2.x + a2.width);
    long y2 = std::min(y + height, a2.y + a2.height);
    x2 -= a.x;
    y2 -= a.y;
    a.width = (x2 < 0 ? 0 : x2);
    a.height = (y2 < 0 ? 0 : y2);
    return a;
  }
  bool intersects(const Area& a2) const {
    return intersection(a2).area() > 0;
  }
  bool contains(const Area& a2) const {
    return intersection(a2) == a2;
  }
  void dump(FILE* f = stdout, bool eol = true) const {
    fprintf(f, "Area(x=%ld, y=%ld, w=%ld, h=%ld)", x, y, width, height);
    if (eol) fputc('\n', f);
    fflush(f);
  }
};

struct MonitorInfo {
  Area desktop;
  std::vector<Area> screens;
  std::vector<Area> usable_areas;
  bool operator==(const MonitorInfo& other) const {
    if (desktop != other.desktop) return false;
    if (screens != other.screens) return false;
    if (usable_areas != other.usable_areas) return false;
    return true;
  }
  bool operator!=(const MonitorInfo& other) const {
    return !(*this == other);
  }
  void dump(FILE* f = stdout, bool eol = true) const {
    fprintf(f,"MonitorInfo(\n");
    fprintf(f,"  desktop=");
    desktop.dump(f);
    fprintf(f,"  screens=(\n");
    for (size_t i=0; i < screens.size(); ++i) {
      fprintf(f,"    [%d]=", (int)i);
      screens[i].dump(f);
    }
    fprintf(f,"  )\n");
    fprintf(f,"  usable_areas=(\n");
    for (size_t i=0; i < usable_areas.size(); ++i) {
      fprintf(f,"    [%d]=", (int)i);
      usable_areas[i].dump(f);
    }
    fprintf(f,"  )\n");
    fprintf(f,")");
    if (eol) fputc('\n', f);
    fflush(f);
  }
};

struct BorderInfo {
  unsigned long left;
  unsigned long right;
  unsigned long top;
  unsigned long bottom;
};

// We use the old MOTIF_WM_HINTS technique to remove our border without doing
// an override-redirect so that we remain under WM control.
struct MotifHints {
  unsigned int flags;
  unsigned int functions;
  unsigned int decorations;
  int inputMode;
  unsigned int status;
};

#define _NET_WM_STATE_REMOVE    0
#define _NET_WM_STATE_ADD       1
#define _NET_WM_STATE_TOGGLE    2
#define MAX_PROPERTY_VALUE_LEN  4096  // From libX11 documentation.

Atom _NET_WM_STATE;
Atom _NET_WM_STATE_MAXIMIZED_VERT;
Atom _NET_WM_STATE_MAXIMIZED_HORZ;
Atom _NET_WM_STATE_SKIP_TASKBAR;
Atom _NET_WM_STATE_SKIP_PAGER;
Atom _NET_WM_STATE_BELOW;
Atom _NET_WM_MOVERESIZE;
Atom _MOTIF_WM_HINTS;

void GetAtoms(Display* display) {
  _NET_WM_STATE =
      XInternAtom(display, "_NET_WM_STATE", False);
  _NET_WM_STATE_MAXIMIZED_VERT =
      XInternAtom(display, "_NET_WM_STATE_MAXIMIZED_VERT", False);
  _NET_WM_STATE_MAXIMIZED_HORZ =
      XInternAtom(display, "_NET_WM_STATE_MAXIMIZED_HORZ", False);
  _NET_WM_STATE_SKIP_TASKBAR =
      XInternAtom(display, "_NET_WM_STATE_SKIP_TASKBAR", False);
  _NET_WM_STATE_SKIP_PAGER =
      XInternAtom(display, "_NET_WM_STATE_SKIP_PAGER", False);
  _NET_WM_STATE_BELOW =
      XInternAtom(display, "_NET_WM_STATE_BELOW", False);
  _NET_WM_MOVERESIZE =
      XInternAtom(display, "_NET_WM_MOVERESIZE", False);
  _MOTIF_WM_HINTS = 
      XInternAtom(display, "_MOTIF_WM_HINTS", False);
  return;
}

// This returns the next XEvent with a maximum timeout. Returns true if an
// event was returned, false on timeout.
bool XNextEventTimeout(Display* display, double timeout, XEvent* xev) {
  assert(xev != NULL);
  assert(timeout >= 0);

  // Get the file descriptor for the X11 connection, and make an fd_set
  // containing it.
  int fd = ConnectionNumber(display);
  fd_set fds;
  FD_ZERO(&fds);
  FD_SET(fd, &fds);

  // Convert the timeout from seconds to a timeval.
  timeval tv;
  tv.tv_sec = floor(timeout);
  tv.tv_usec = round((timeout - tv.tv_sec) * 1e6);

  // There might already be something waiting. If so, use it.
  if (XPending(display)) {
    XNextEvent(display, xev);
    return true;
  }

  // Select on the input.
  select(fd + 1, &fds, NULL, NULL, &tv);

  if (XPending(display)) {
    XNextEvent(display, xev);
    return true;
  }

  return false;
}

bool SendClientMessage(Display* display, Window window,
                       Atom message,
                       unsigned long data0, unsigned long data1,
                       unsigned long data2, unsigned long data3,
                       unsigned long data4) {
  assert(display != NULL);
  assert(window != 0);

  XEvent xev;
  memset(&xev, 0, sizeof(xev));
  xev.xclient.type = ClientMessage;
  xev.xclient.serial = 0;
  xev.xclient.send_event = True;
  xev.xclient.message_type = message;
  xev.xclient.window = window;
  xev.xclient.format = 32;  // this is 32 even when longs are 64 bit!
  xev.xclient.data.l[0] = data0;
  xev.xclient.data.l[1] = data1;
  xev.xclient.data.l[2] = data2;
  xev.xclient.data.l[3] = data3;
  xev.xclient.data.l[4] = data4;
  PushErrorWrap(XSendEvent, display, DefaultRootWindow(display), False,
                SubstructureRedirectMask | SubstructureNotifyMask, &xev);
  return true;
}

bool SendClientMessage(Display* display, Window window,
                       const char* message,
                       unsigned long data0, unsigned long data1,
                       unsigned long data2, unsigned long data3,
                       unsigned long data4) {
  assert(display != NULL);
  assert(message != NULL);

  Atom message_atom = XInternAtom(display, message, False);
  return SendClientMessage(display, window, message_atom,
                           data0, data1, data2, data3, data4);
}

bool SendStateMessage(Display* display, Window window,
                      unsigned long action,
                      unsigned long prop1, unsigned long prop2) {
  assert(display != NULL);
  assert(window != 0);
  assert(action == _NET_WM_STATE_REMOVE || action == _NET_WM_STATE_ADD ||
         action == _NET_WM_STATE_TOGGLE);
  PushErrorWrap(SendClientMessage, display, window, "_NET_WM_STATE", action,
                prop1, prop2, 0, 0);
  return true;
}

// A simple get property function.
bool GetRawProperty(Display* display, Window window,
                    Atom propertyType, const char* propertyName,
                    std::vector<unsigned char>* data) {
  Atom property = XInternAtom(display, propertyName, False);
  Atom returnType;
  int returnFormat;
  unsigned long returnCount;
  unsigned long returnBytesAfter;
  unsigned char* returnProperty;
  Status s;
  s = XGetWindowProperty(display, window, property, 0,
                         MAX_PROPERTY_VALUE_LEN / 4, False,
                         propertyType, &returnType, &returnFormat,
                         &returnCount, &returnBytesAfter, &returnProperty);
  if (s != Success) {
    PushError("XGetWindowProperty failed with %d", s);
    if (returnProperty) XFree(returnProperty);
    return false;
  }

  if (propertyType != returnType) {
    PushError("returned property type does not match expected type");
    if (returnProperty) XFree(returnProperty);
    return false;
  }

  if (returnProperty == NULL) {
    PushError("no property returned");
    if (returnProperty) XFree(returnProperty);
    return false;
  }

  // There is peculiar problem here in 64-bit mode.  Namely,
  // the returnFormat reports 32 when it actually means 8*sizeof(long)
  // See http://mail.gnome.org/archives/wm-spec-list/2003-March/msg00067.html
  int n;
  if (returnFormat == 32)
    n = sizeof(long) * returnCount;
  else
    n = (returnFormat / 8) * returnCount;

  if (n == 0) {
    XFree(returnProperty);
    PushError("property has zero length");
    return false;
  }

  data->resize(n);
  memcpy(reinterpret_cast<void*>(&(*data)[0]),
         reinterpret_cast<void*>(returnProperty), n);

  XFree(returnProperty);

  return true;
}

// Does the assignment from a data buffer to a data pointer.
template<typename VALUE_TYPE>
struct CastPropertyFunctor {
  bool operator()(const std::vector<unsigned char> &data,
                  VALUE_TYPE* value) {
    if ((data.size() % sizeof(VALUE_TYPE)) != 0) {
      PushError("data length (%d) does not match value size (%d)",
                (int)data.size(), (int)sizeof(VALUE_TYPE));
      return false;
    }
    *value = *reinterpret_cast<const VALUE_TYPE*>(&data[0]);
    return true;
  }
};
template<typename VALUE_TYPE>
struct CastPropertyFunctor<std::vector<VALUE_TYPE> > {
  bool operator()(const std::vector<unsigned char> &data,
                  std::vector<VALUE_TYPE>* value) {
    size_t n = data.size();
    if ((n % sizeof(VALUE_TYPE)) != 0) {
      PushError("data length (%d) not a multiple of value size (%d)",
                (int)data.size(), (int)sizeof(VALUE_TYPE));
      return false;
    }
    n /= sizeof(VALUE_TYPE);
    value->resize(n);
    for (size_t i = 0; i < n; ++i)
      (*value)[i] = *reinterpret_cast<const VALUE_TYPE*>(
          &data[i*sizeof(VALUE_TYPE)]);
    return true;
  }
};
template<>
struct CastPropertyFunctor<std::string> {
  bool operator()(const std::vector<unsigned char> &data,
                  std::string* value) {
    *value = std::string(
        reinterpret_cast<const char*>(&data[0]),
        data.size());
    return true;
  }
};

// Returns a property
template<typename VALUE_TYPE>
bool GetProperty(Display* display, Window window,
                 Atom propertyType, const char* propertyName,
                 VALUE_TYPE* value) {
  assert(value != NULL);

  std::vector<unsigned char> data;
  PushErrorWrap(GetRawProperty, display, window, propertyType, propertyName,
                &data);
  PushErrorWrap(CastPropertyFunctor<VALUE_TYPE>(), data, value);
  return true;
}


bool MaximizeWindow(Display* display, Window window) {
  assert(display != NULL);
  assert(window != 0);
  PushErrorWrap(SendStateMessage, display, window, _NET_WM_STATE_ADD,
                _NET_WM_STATE_MAXIMIZED_VERT,
                _NET_WM_STATE_MAXIMIZED_HORZ);
  return true;
}

bool DemaximizeWindow(Display* display, Window window) {
  assert(display != NULL);
  assert(window != 0);
  PushErrorWrap(SendStateMessage, display, window, _NET_WM_STATE_REMOVE,
                _NET_WM_STATE_MAXIMIZED_VERT,
                _NET_WM_STATE_MAXIMIZED_HORZ);
  return true;
}

bool GetUndecoratedGeometry(Display* display, Window window, Area* area) {
  Window root;
  int x, y;
  unsigned int w, h, bw, d;
  PushErrorWrap(XGetGeometry, display, window, &root,
                &x, &y, &w, &h, &bw, &d);
  area->x = x;
  area->y = y;
  area->width = w;
  area->height = h;
  return true;
}

bool GetDecoratedGeometry(Display* display, Window window, Area* area) {
  GetUndecoratedGeometry(display, window, area);

  // Get the decoration extents.  This can fail if the WM doesn't actually
  // control the window, in which case the WM extents are zero.
  BorderInfo borders;
  if (GetProperty(display, window, XA_CARDINAL,
                  "_NET_FRAME_EXTENTS", &borders)) {
    area->x -= borders.left;
    area->y -= borders.top;
    area->width += borders.left + borders.right;
    area->height += borders.top + borders.bottom;
  }
  return true;
}

class ScopedWindow {
 private:
  Display* display_;
  Window window_;

 public:
  ScopedWindow(Display* display)
      : display_(display),
        window_(None) {
    assert(display != NULL);
  }

  ScopedWindow(Display* display, Window window)
      : display_(display),
        window_(window) {
    assert(display != NULL);
  }

  ~ScopedWindow() {
    Release();
  }

  ScopedWindow& operator=(Window window) {
    Release();
    window_ = window;
    return *this;
  }

  void Set(Window window) {
    Release();
    window_ = window;
  }

  Window Get() const {
    return window_;
  }

  void Release() {
    if (window_ != None) {
      if (!XDestroyWindow(display_, window_))
        CloseDisplayAndDie(display_, "ScopedWindow: XDestroyWindow failed");
      window_ = None;
    }
  }

  operator Window() const {
    return window_;
  }
};

// This is only used by GetUsableArea! It assumes that the window, if generated,
// lives in a ScopedWindow and will destroy itself on return.
#define WaitForEvent(display, timeout, test) { \
          while (true) { \
            XEvent xev; \
            if (!XNextEventTimeout(display, timeout, &xev)) { \
              PushError("XNextEventTimeout timed out"); \
              return false; \
            } \
            if (test) \
              break; \
          } \
        }

// Given a physical screen Area, determines the size of the usable desktop
// within it. This is a bit of a hack for now--it actually creates a blank full
// screen window for a brief moment and queries it for its size.
// This assumes that we are set to receive StructureNotify and
// SubstructureNotify events.
// TODO(chrisha): Find a way to get this information directly from the WM!
bool GetUsableArea(Display* display, const Area& screen, Area* usable) {
  assert(display != NULL);
  assert(usable != NULL);

  const double timeout = 0.5;

  // By default, we stick with the initial screen size.
  *usable = screen;

  // Create a basic input-only window.
  XSetWindowAttributes xswa;
  xswa.override_redirect = False;
  Window window = XCreateWindow(
      display, DefaultRootWindow(display), 0, 0, 50, 50, 0,
      CopyFromParent, InputOutput, CopyFromParent,
      CWOverrideRedirect, &xswa);
  if (window == None) {
    PushError("XCreateWindow failed");
    return false;
  }
  ScopedWindow scoped_window(display, window);
  WaitForEvent(display, timeout,
      xev.type == CreateNotify && xev.xcreatewindow.window == window);

  // Indicate that we do not want focus.
  XWMHints xwm_hints;
  xwm_hints.flags = InputHint;
  xwm_hints.input = False;
  PushErrorWrap(XSetWMHints, display, window, &xwm_hints);

  // Indicate that we should not show up in the pager or the taskbar, and
  // that we should appear completely in the background.
  PushErrorWrap(XChangeProperty, display, window, _NET_WM_STATE, XA_ATOM, 32,
      PropModeAppend, (unsigned char*)&_NET_WM_STATE_SKIP_TASKBAR, 1);
  PushErrorWrap(XChangeProperty, display, window, _NET_WM_STATE, XA_ATOM, 32,
      PropModeAppend, (unsigned char*)&_NET_WM_STATE_SKIP_PAGER, 1);
  PushErrorWrap(XChangeProperty, display, window, _NET_WM_STATE, XA_ATOM, 32,
      PropModeAppend, (unsigned char*)&_NET_WM_STATE_BELOW, 1);

  // Indicate that we are not to be decorated.
  MotifHints motif_hints;
  motif_hints.flags = 2;
  motif_hints.decorations = 0;
  PushErrorWrap(XChangeProperty, display, window, _MOTIF_WM_HINTS,
      XA_CARDINAL, 32, PropModeReplace, (unsigned char*)&motif_hints, 5);
  
  // Map the window and wait for it to appear.
  PushErrorWrap(XMapWindow, display, window);
  WaitForEvent(display, timeout,
      xev.type == MapNotify && xev.xmap.window == window);

  // Move to the middle of the screen we are interested in.
  PushErrorWrap(XMoveWindow, display, window,
      screen.x + screen.width / 2, screen.y + screen.height / 2);
  WaitForEvent(display, timeout,
      xev.type == ConfigureNotify && xev.xconfigure.window == window);

  // Maximize it.
  PushErrorWrap(MaximizeWindow, display, window);
  WaitForEvent(display, timeout,
      xev.type == ConfigureNotify && xev.xconfigure.window == window);

  // Get the window geometry.
  GetDecoratedGeometry(display, window, usable);

  // If the window did not resize, or the screen does not contain the window,
  // then this information is meaningless. Default to using the whole screen
  // size.
  if ((usable->width < 100 && usable->height == 100) ||
      !screen.contains(*usable)) {
    // TODO(chrisha): Logging.
    *usable = screen;
  }

  // Unmap and destroy the window.
  PushErrorWrap(XUnmapWindow, display, window);
  WaitForEvent(display, timeout,
      xev.type == UnmapNotify && xev.xunmap.window == window);
  scoped_window.Release();
  WaitForEvent(display, timeout,
      xev.type == DestroyNotify && xev.xdestroywindow.window == window);

  return true;
}

// Gets the active window.
bool GetActiveWindow(Display* display, Window* active) {
  assert(display != NULL);
  assert(active != NULL);

  *active = 0;
  PushErrorWrap(GetProperty, display, DefaultRootWindow(display), XA_WINDOW,
                "_NET_ACTIVE_WINDOW", active);
  return true;
}

// Returns the size and position of the current desktop.
bool GetDesktopInfo(Display* display, Area* area) {
  *area = {0, 0, 0, 0};

  Window root = DefaultRootWindow(display);

  std::vector<Area> workareas;
  PushErrorWrap(GetProperty, display, root, XA_CARDINAL,
                   "_NET_WORKAREA", &workareas);
  
  if (workareas.size() == 1) {
    *area = workareas[0];
  } else {
    long currentDesktop;
    if (!GetProperty(display, root, XA_CARDINAL,
                     "_NET_CURRENT_DESKTOP",
                     &currentDesktop) &&
        !GetProperty(display, root, XA_CARDINAL,
                     "_WIN_WORKSPACE",
                     &currentDesktop)) {
      PushError("failed to get _NET_CURRENT_WORKSPACE/_WIN_WORKSPACE");
      return false;
    }
    if (currentDesktop > workareas.size()) {
      PushError("current desktop (%d) has no info (%d provided)",
                (int)currentDesktop, (int)workareas.size());
    }

    *area = workareas[currentDesktop];
  }

  return true;
}

// For each window, keep track of the last key pressed, and the
// number of times in a row it has been pressed (minus 1).
struct CommandInfo {
  int digit;
  int count;

  CommandInfo()
      : digit(0),
        count(0) {
  }

  int process(int d) {
    if (digit == d)
      return ++count;
    digit = d;
    count = 0;
    return count;
  }
};
typedef std::map<Window, CommandInfo> WindowCommandInfo;
WindowCommandInfo gWindowCommandInfo;

void CalcOffsets(int length, int cells, std::vector<int>* offsets) {
  assert(length > 0);
  assert(cells > 0);
  assert(cells < length);
  assert(offsets != NULL);
  offsets->resize(cells+1);
  int i, j;
  (*offsets)[0] = 0;
  for (i = cells, j = 0; i >= 1; --i, ++j) {
    int n = length / i;
    (*offsets)[j + 1] = (*offsets)[j] + n;
    length -= n;
  }
}

void GetOffsetAndLength(const std::vector<int> &offsets, int c0, int c1,
                        int* lo, int* l) {
  assert(offsets.size() >= 2);
  assert(c0 >= 0);
  assert(c0 < c1);
  assert(c1 < offsets.size());
  assert(lo != NULL);
  assert(l != NULL);

  *lo = 0;
  *l = 0;
  int cd = static_cast<int>(offsets.size()-1);
  *lo = offsets[c0];
  *l = offsets[c1]-offsets[c0];
}


bool PlaceWindow(Display* display, Window window,
                 const Area& area,
                 int wd, int w0, int w1,
                 int hd, int h0, int h1) {
  assert(display != NULL);
  assert(window != 0);
  assert(wd > 0);
  assert(w0 >= 0 && w0 < w1);
  assert(w1 <= wd);
  assert(hd > 0);
  assert(h0 >= 0 && h0 < h1);
  assert(h1 <= hd);

  // Are we actually maximizing the window?
  if (wd == 1 && hd == 1) {
    PushErrorWrap(MaximizeWindow, display, window);
    return true;
  }

  // Ensure we are a free floating window before doing placement
  PushErrorWrap(DemaximizeWindow, display, window);

  std::vector<int> xs(wd+1);
  std::vector<int> ys(hd+1);
  CalcOffsets(area.width, wd, &xs);
  CalcOffsets(area.height, hd, &ys);

  // Calculate desired position *within* workspace of geometry
  // of *decorated* window
  int nx, ny, nw, nh;
  GetOffsetAndLength(xs, w0, w1, &nx, &nw);
  GetOffsetAndLength(ys, h0, h1, &ny, &nh);

  // Get the frame extents.  This can fail if the WM doesn't actually
  // control the window, in which case the WM extents are zero.
  BorderInfo borders;
  if (!GetProperty(display, window, XA_CARDINAL,
                   "_NET_FRAME_EXTENTS", &borders))
    borders = {0, 0, 0, 0};

  // Get the location within the workspace.
  // We control the location of the *decorated* upper-left corner,
  // but the width/height is for the *undecorated* inner window.
  int dx = nx;
  int dy = ny;
  int dw = nw - borders.left - borders.right;
  int dh = nh - borders.top - borders.bottom;

  // Transform this to *absolute* screen coordinates
  dx += area.x;
  dy += area.y;

  // MoveResize is in *absolute* screen coordinates.
  PushErrorWrap(XMoveResizeWindow, display, window, dx, dy, dw, dh);
  XFlush(display);

  return true;
}

bool PlaceWindow(Display* display, Window window, const MonitorInfo& monitors) {
  assert(display != NULL);

  int digit = gWindowCommandInfo[window].digit;
  int i = gWindowCommandInfo[window].count;

  // Get the width and denominator
  int w, wd;
  if (digit != 2 && digit != 5 && digit != 8) {
    static const int widths[] = { 1, 1, 2 };
    static const int denoms[] = { 2, 3, 3 };
    w = widths[i%3];
    wd = denoms[i%3];
  } else {
    static const int denoms[] = { 1, 3 };
    w = 1;
    wd = denoms[i%2];
  }

  // Get height and denominator
  int h, hd;
  if (digit != 4 && digit != 5 && digit != 6) {
    h = 1;
    hd = 2;
  } else {
    h = 1;
    hd = 1;
  }

  // Do horizontal placement
  int w0, w1;
  switch (digit) {
    case 1:
    case 4:
    case 7: {
      w0 = 0;
      w1 = w;
      break;
    }

    case 2:
    case 5:
    case 8: {
      w0 = (wd-w)/2;
      w1 = w0 + w;
      break;
    }

    case 3:
    case 6:
    case 9: {
      w1 = wd;
      w0 = w1-w;
      break;
    }
  }

  // Do vertical placement
  int h0, h1;
  if (digit > 3) {
    h0 = 0;
    h1 = h;
  } else {
    h1 = hd;
    h0 = hd-h;
  }

  // TODO(chrisha): Break this out into a function!
  int out_screen = 0;
  if (monitors.usable_areas.size() > 1) {
    Window root;
    int x, y;
    unsigned int w, h, bw, d;
    PushErrorWrap(XGetGeometry, display, window, &root,
                  &x, &y, &w, &h, &bw, &d);
    PushErrorWrap(XTranslateCoordinates, display, window,
                  DefaultRootWindow(display), x, y, &x, &y, &root);

    Area window_area = {x, y, w, h};

    // Keep track of the screen in which the window mostly lies.
    int max_int_size = -1;
    for (size_t i = 0; i < monitors.usable_areas.size(); ++i) {
      Area a = window_area.intersection(monitors.usable_areas[i]);
      int int_size = window_area.intersection(monitors.usable_areas[i]).area();
      if (int_size > max_int_size) {
        max_int_size = int_size;
        out_screen = (int)i;
      }
    }
  }

  // Do the actual placement of the window.
  PushErrorWrap(PlaceWindow, display, window, monitors.usable_areas[out_screen],
                wd, w0, w1, hd, h0, h1);

  return true;
}

// Process a window digit command (digit is 1-9).
bool ProcessWindowDigit(Display* display, Window window,
                        const MonitorInfo& monitors, int digit) {
  gWindowCommandInfo[window].process(digit);
  PlaceWindow(display, window, monitors);

  return true;
}

// Find the active window, and place it.
bool ProcessDigit(Display* display, const MonitorInfo& monitors, int digit) {
  // Find window with focus
  Window focus;
  PushErrorWrap(GetActiveWindow, display, &focus);

  // No window is currently active?  Do nothing.
  if (focus == 0)
    return true;

  // Only process a window if it's not the desktop
  if (DefaultRootWindow(display) != focus)
    PushErrorWrap(ProcessWindowDigit, display, focus, monitors, digit);

  return true;
}

bool EnsureXrandr(Display* display, int* ev_base, int* err_base) {
  assert(ev_base != NULL);
  assert(err_base != NULL);
  int major, minor;
  PushErrorWrap(XRRQueryVersion, display, &major, &minor);
  if (major < 1 || (major == 1 && minor < 3)) {
    PushError("Require Xrandr version 1.3 or greater");
    return false;
  }
  PushErrorWrap(XRRQueryExtension, display, ev_base, err_base);
  return true;
}

bool GetXrandrInfo(Display* display, std::vector<Area>* screens) {
  assert(screens != NULL);

  screens->clear();

  // Get a list of outputs.
  XRRScreenResources* res = XRRGetScreenResources(display,
                                                  DefaultRootWindow(display));
  if (res == NULL) {
    PushError("XRRGetScreenResources failed");
    return false;
  }

  // Iterate over the outputs.
  for (int i = 0; i < res->noutput; ++i) {
    XRROutputInfo* output_info = XRRGetOutputInfo(display, res,
                                                  res->outputs[i]);
    if (output_info == NULL) {
      PushError("XRRGetOutputInfo failed");
      return false;
    }

    // If connected and enabled (has valid CRTC), get screen size and position.
    if (output_info->connection == RR_Connected && output_info->crtc != None) {
      XRRCrtcInfo* crtc = XRRGetCrtcInfo(display, res, output_info->crtc);
      if (crtc == NULL) {
        PushError("XRRGetCrtcInfo failed");
        return false;
      }
      Area screen({crtc->x, crtc->y, crtc->width, crtc->height});
      screens->push_back(screen);
      XRRFreeCrtcInfo(crtc);
    }

    XRRFreeOutputInfo(output_info);
  }
  XRRFreeScreenResources(res);

  return true;
}

bool GetMonitorInfo(Display* display, MonitorInfo* monitors) {
  assert(display != NULL);
  assert(monitors != NULL);

  PushErrorWrap(GetDesktopInfo, display, &monitors->desktop);
  PushErrorWrap(GetXrandrInfo, display, &monitors->screens);

  // For each physical screen, get the usable area.
  monitors->usable_areas.resize(monitors->screens.size());
  for (size_t i = 0; i < monitors->screens.size(); ++i)
    PushErrorWrap(GetUsableArea, display, monitors->screens[i],
                  &monitors->usable_areas[i]);

  return true;
}

// Hot key information
static const unsigned int gHotkeyModifiers = ControlMask | Mod1Mask | Mod2Mask;
static const int gHotkeyCount = 9;
static const int gHotkeySyms[gHotkeyCount] = {
  XK_KP_1, XK_KP_2, XK_KP_3,
  XK_KP_4, XK_KP_5, XK_KP_6,
  XK_KP_7, XK_KP_8, XK_KP_9
};
static int gHotkeyCodes[gHotkeyCount];// = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

int
main(
  int argc,
  const char **argv
)
{
  Display* display = XOpenDisplay(NULL);
  Status s;
  if (!display)
    Die("unable to open X display");

  // Set up the atoms we'll use often.
  GetAtoms(display);

  // Do we have multiple screens?
  if (ScreenCount(display) > 1) {
    // Bail, because we presently can't handle multiple screens.
    CloseDisplayAndDie(display, "Can't handle multiple screens");
  }

  // Ensure we have Xrandr.
  int xrr_ev_base = 0;
  int xrr_err_base = 0;
  if (!EnsureXrandr(display, &xrr_ev_base, &xrr_err_base))
    CloseDisplayAndDie(display, "EnsureXrandr failed");

  // Set up our event loop. We want to monitor keypress events, window close
  // events, and Xrandr screen change events. The input mask must be set before
  // calling GetMonitorInfo, as it relies on events.
  XSelectInput(display, DefaultRootWindow(display),
               KeyPressMask | StructureNotifyMask | SubstructureNotifyMask);
  XRRSelectInput(display, DefaultRootWindow(display),
                 RRCrtcChangeNotifyMask);

  // This information is *slow* to get, so we're going to have
  // to get it once and then subscribe to XRROutputChangeNotify events.
  // Whenever one of those comes, we'll simply have to regather all
  // appropriate information.
  MonitorInfo monitors;
  if (!GetMonitorInfo(display, &monitors))
    CloseDisplayAndDie(display, "GetMonitorInfo failed");

  // Set up our global hotkeys.
  for (int i = 0; i < gHotkeyCount; ++i) {
    gHotkeyCodes[i] = XKeysymToKeycode(display, gHotkeySyms[i]);
    if (!XGrabKey(display, gHotkeyCodes[i], gHotkeyModifiers,
                  DefaultRootWindow(display),
                  True, GrabModeAsync, GrabModeAsync)) {
      CloseDisplayAndDie(display, "unable to grab hotkey [%c]", gHotkeySyms[i]);
    }
  }

  while (true) {
    XEvent xev;
    XNextEvent(display, &xev);

    if (xev.type == KeyPress) {
      if (xev.xkey.state != gHotkeyModifiers)
        break;
      for (int i = 0; i < gHotkeyCount; ++i) {
        if (xev.xkey.keycode == gHotkeyCodes[i])
          if (!ProcessDigit(display, monitors, i+1))
            CloseDisplayAndDie(display, "ProcessDigit failed");
      }
    } else if (xev.type == DestroyNotify) {
      Window w = xev.xdestroywindow.window;
      gWindowCommandInfo.erase(w);
    } else if (xev.type == ConfigureNotify) {
      // If the root window changes shape/size, then gather new information
      // regarding all outputs.
      if (xev.xconfigure.window == DefaultRootWindow(display)) {
        MonitorInfo mi;
        if (!GetMonitorInfo(display, &mi))
          CloseDisplayAndDie(display, "GetMonitorInfo failed");
        if (monitors != mi) {
          monitors = mi;
        }
      }
    }
  }

  XCloseDisplay(display);

  return 0;
}
